# -*-coding:utf-8 -*-
from numpy import *

# 第一部分
"""
函数说明：加载数据集
"""
def loadDataSet():
    return [[1, 3, 4], [2, 3, 5], [1, 2, 3, 5], [2, 5]]
"""
函数说明：构建集合C1。即所有候选项元素的集合。
parameters：
    dataSet -数据集
return:
    frozenset列表
output:
    [forzenset([1]),forzenset([2]),……]
"""
def createC1(dataSet):
    C1 = []                     #创建一个空列表
    for transaction in dataSet: #对于数据集中的每条记录
        for item in transaction:#对于每条记录中的每一个项
            if not [item] in C1:       #如果该项不在C1中，则添加
                C1.append([item])
    C1.sort()                   #对集合元素排序
    return list(map(frozenset,C1))    #将C1的每个单元列表元素映射到forzenset()
"""
函数说明：获取列表在数据集中出现的次数
parameters:
    D -数据集
    l -列表
return:
    cnt -列表在数据集中出现的次数
"""
def solveFitCnt(D, l):
    cnt = 0 # 出现次数
    
    for item in D:
        for elem in l:
            if elem not in item:#如有一个elem不在item中，则本次判断终止
                cnt-=1 #抵消之后的++
                break
        cnt+=1 #默认出现次数+1
    return cnt
"""
函数说明：构建符合支持度的集合Lk
parameters:
    D -数据集
    Ck -候选项集列表
    minSupport -感兴趣项集的最小支持度
return:
    retList -符合支持度的频繁项集合列表L
    supportData -最频繁项集的支持度
"""
def scanD(D,Ck,minSupport):
    ssCnt = {}                                              #创建空字典
    #在下面添加代码，遍历数据集中的交易记录，统计Ck中候选集的计数，结果存放在ssCnt中
    for key in Ck:
        ssCnt[key] = solveFitCnt(D, key)

    numItems = float(len(D))                                #得到数据集中交易记录的条数
    retList = []                                            #新建空列表
    supportData = {}                                        #新建空字典用来存储最频繁集和支持度
    for key in ssCnt:
        support = ssCnt[key] / numItems                     #计算每个元素的支持度
        if support >= minSupport:                           #如果大于最小支持度则添加到retList中
            retList.insert(0,key)
        supportData[key] = support                          #并记录当前支持度，索引值即为元素值
    return retList,supportData

# if __name__ == '__main__':
#     dataSet = loadDataSet()
#     print("数据集:\n",dataSet)
#     C1 = createC1(dataSet)
#     print("候选集C1:\n",C1)
#     D = list(map(set,dataSet))  #将数据转换为集合形式
#     L1,supportData = scanD(D,C1,0.5)
#     print("满足最小支持度为0.5的频繁项集L1：\n",L1)

# 第二部分
"""
函数说明：判断两个相同长度的列表前k-1个元素是否相同，其中k是列表长度
parameters:
    l1 -列表1
    l2 -列表2
return:
    flag -相等标志
"""
def matchK(l1, l2):
    lenToMatch = len(l1) - 1 #待匹配字符串长度

    for i in range(lenToMatch):
        if l1[i] != l2[i]:
            return False
    return True
"""
函数说明:构建集合Ck
parameters:
    Lk -频繁项集列表L
    k -候选集的列表中元素项的个数
return:
    retList -候选集项列表Ck
"""
def aprioriGen(Lk,k):
    retList = []                                            #创建一个空列表
    lenLk = len(Lk)                                         #得到当前频繁项集合列表中元素的个数
    #在下面添加代码，遍历Lk，比较每两个项集，如果符合合并要求，则用集合合并操作|来产生k+1项集，并存入retList
    #[注]此处需要比较两个项集的前k-2个元素，试说明原因
    # 自己思路
    # Lk.sort() #排序，保证单元按顺序递增
    # for i in range(lenLk):
    #     for j in range(i, lenLk):
    #         if(matchK(Lk[i], Lk[j]) == True):
    #             print(Lk[i], end = " ")
    #             temp = list(Lk[i])
    #             temp.extend(Lk[j])
    #             retList.append(list(map(frozenset, list(set(temp)))))#合并两项

    # 老师思路
    for i in range(lenLk):
        for j in range(i + 1, lenLk):# 疑问：不先sort，直接j从i+1开始
            L1 = list(Lk[i])[:k - 2]; L2 = list(Lk[j])[:k - 2]
            #比较集合的前k-2个元素
            L1.sort(); L2.sort()
            if(L1 == L2):
                retList.append(Lk[i] | Lk[j])#集合合并

    return retList
"""
函数说明：apriori算法实现
parameters:
    dataSet -数据集
    minSupport -最小支持度
return:
    L -候选项集的列表
    supportData -项集支持度
"""
def apriori(dataSet,minSupport=0.5):
    C1 = createC1(dataSet)
    D = list(map(set,dataSet))                  #将数据集转化为集合列表
    L1, supportData = scanD(D,C1,minSupport)    #调用scanD()函数，过滤不符合支持度的候选项集
    L = [L1]                                    #将过滤后的L1放入L列表中
    k = 2                                       #最开始为单个项的候选集，需要多个元素组合
    while(len(L[k-2])>0):
        Ck = aprioriGen(L[k-2],k)               #创建Ck
        Lk, supK = scanD(D,Ck,minSupport)       #由Ck得到Lk
        supportData.update(supK)                #更新支持度
        L.append(Lk)                            #将Lk放入L列表中
        k += 1                                  #继续生成L3，L4....
    return L, supportData

# if __name__ == '__main__':
#     dataSet = loadDataSet()
#     print("数据集:\n",dataSet)
#     C1 = createC1(dataSet)
#     print("候选集C1:\n",C1)
#     D = list(map(set,dataSet))  #将数据转换为集合形式
#     L1,supportData = scanD(D,C1,0.5)
#     print("满足最小支持度为0.5的频繁项集L1：\n",L1)
#     L,suppData = apriori(dataSet)
#     print("满足最小支持度为0.5的频繁项集列表L：\n",L)
#     print("L2:\n",L[1])
#     print("使用L2生成的C3:\n",aprioriGen(L[1],3))

# 第三部分
"""
函数说明：规则构建函数
parameters:
    freqSet -频繁项集合
    H -可以出现在规则右部的元素列表
    supportData -支持度字典
    brl -规则列表
    minConf -最小可信度
return:
    null
"""
def rulesFromConseq(freqSet,H,supportData,brl,minConf=0.7):
    m = len(H[0])                                               #得到H中的频繁集大小m
    if (len(freqSet) > (m+1)):                                  #查看该频繁集是否大到可以移除大小为m的子集
        Hmp1 = aprioriGen(H, m+1)                               #构建候选集Hm+1，Hmp1中包含所有可能的规则
        Hmp1 = calcConf(freqSet,Hmp1,supportData,brl,minConf)   #测试可信度以确定规则是否满足要求
        if (len(Hmp1)>1):                                       #如果不止一条规则满足要求，使用函数迭代判断是否能进一步组合这些规则
            rulesFromConseq(freqSet,Hmp1,supportData,brl,minConf)
        
"""
函数说明：计算规则的可信度，找到满足最小可信度要求的规则
parameters：
    freqSet -频繁项集合
    H -可以出现在规则右部的元素列表
    supportData -支持度字典
    brl -规则列表
    minConf -最小可信度
return:
    prunedH -满足要求的规则列表
"""
def calcConf(freqSet,H,supportData,brl,minConf=0.7):
    prunedH = []                                                #为保存满足要求的规则创建一个空列表
    for conseq in H: 
        conf = supportData[freqSet]/supportData[freqSet-conseq] #可信度计算[support(PUH)/support(P)]
        if conf>=minConf:
            print(freqSet-conseq,'-->',conseq,'可信度为:',conf)
            brl.append((freqSet-conseq,conseq,conf))            #对bigRuleList列表进行填充
            prunedH.append(conseq)                              #将满足要求的规则添加到规则列表
    return prunedH
"""
函数说明：关联规则生成函数
parameters:
    L -频繁项集合列表
    supportData -支持度字典
    minConf -最小可信度
return:
    bigRuleList -包含可信度的规则列表
"""
def generateRules(L,supportData,minConf=0.7):
    bigRuleList = []                                        #创建一个空列表
    for i in range(1,len(L)):                               #遍历频繁项集合列表
        for freqSet in L[i]:                                #遍历频繁项集合
            H1 = [frozenset([item]) for item in freqSet]    #为每个频繁项集合创建只包含单个元素集合的列表H1
            if (i>1):                                       #要从包含两个或者更多元素的项集开始规则构建过程
                rulesFromConseq(freqSet,H1,supportData,bigRuleList,minConf)
            else:                                           #如果项集中只有两个元素，则计算可信度值，(len(L)=2)
                calcConf(freqSet,H1,supportData,bigRuleList,minConf)
    return bigRuleList

if __name__ == '__main__':
    dataSet = loadDataSet()
    print("数据集:\n",dataSet)
    C1 = createC1(dataSet)
    print("候选集C1:\n",C1)
    L,suppData = apriori(dataSet)
    print("满足最小支持度为0.5的频繁项集列表L：\n",L)
    print("满足最小可信度为0.7的规则列表为:")
    rules = generateRules(L,suppData,0.7)
    print(rules)
    print("满足最小可信度为0.5的规则列表为:")
    rules1 = generateRules(L,suppData,0.5)
    print(rules1)